package com.zx._12_算法.排序;

import com.zx._12_算法.Arrs.IAS;
import java.util.ArrayList;
import java.util.List;
import lombok.extern.slf4j.Slf4j;


/**
 *  https://www.runoob.com/w3cnote/radix-sort.html
 *  是在计数排序基础
 */
@Slf4j
public class Sort9_基数排序 implements IAS {

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 获取最大与最小
        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        // 最高位数
        int digit = getMaxDigit(max);

        // -9~9 20个桶  [0-9]对应负数，[10-19]对应正数 (bucket + 10)
        List<List<Integer>> buck = new ArrayList<>(20);
        for (int i = 0; i < 20; i++) {
            buck.add(new ArrayList<>());
        }

        for (int i = 0; i < digit; i++) {
            int chushu = 1;
            for (int j = 0; j < i; j++) {
                chushu *= 10;
            }

            for (int j = 0; j < arr.length; j++) {
                int num = arr[j];

                // i 位上的数字
                int bit = num / chushu % 10;

                // 一律加十
                bit += 10;

                buck.get(bit).add(num);
            }

            int idx = 0;
            for (List<Integer> b : buck) {
                if (b.size() == 0) {
                    continue;
                }
                for (Integer in : b) {
                    arr[idx] = in;
                    idx++;
                }
                b.clear();
            }

        }

    }


    /**
     * 获取最高位数
     */
    private int getMaxDigit(int num) {
        int len = 1;
        while (true) {
            num = num / 10;
            if (num == 0) {
                break;
            } else {
                len++;
            }
        }
        return len;
    }


}
